"""基于贪心算法优化的欺负算法"""
import random

"""
优化后的算法过程
其基本思想是：
前提：假设运行的进程数为N，当前的协调者的进程号是最大值N。
（1）当一个进程P（假设该进程的进程号为i）发现协调者停止工作时就发起选举，在发起选举前，该进程首先搜索进程号列表，
找出当前进程号最大的进程（崩溃的协调者除外，应该是N-1），然后向该进程发送选举消息。这里就使用了贪心策略，直接找
（看起来）最佳选择。
（2）如果N-1号进程回发消息，则表示新的协调者产生，为N-1号进程，然后第N-1号进程向其他进程发送获胜的消息，并承担
协调者的责任，此时发送的消息数一发一回两条消息。
（3）如果第N-1号进程已经在这之前停止工作，则进程P将收不到回答消息，那它将继续向第N-2号进程发送选举消息，有反馈则
该进程成为新的协调者，此时总的消息数是发送两条，反馈一条，共三条消息。
（4）同样的，如果还是没有反馈，则一直回溯到第i+1号进程。此时已发的消息数为N-i-1，反馈消息为1条，共N-i条消息。
（5）如果第i+1号进程还是没有反馈消息，则第i号进程，即进程P成为新的协调者。此时已发的消息数为N-i-1，没有反馈消息，
共N-i-1条消息。
"""

import time
from datetime import datetime
from threading import Lock, Thread


class Participant:
    def __init__(self, participant_id, coordinator):
        self.coordinator = coordinator  # 协调者对象
        self.participant_id = participant_id  # 参与者id,主线程创建该参与者时提供
        self.participant_list = self.coordinator.participant_list  # 参与者列表
        self.thread_list = self.coordinator.thread_list  # 线程列表，选举时用
        self.thread_id = self.participant_id  # 自己的线程id
        self.coordinator_thread_index = self.coordinator.index  # 协调者线程在线程列表的索引
        self.request_list = self.coordinator.request_list  # 绑定协调者的请求列表
        self.request_time = datetime.now()  # 请求时间
        self.get_response = True  # 是否得到响应
        self.is_using = False  # 是否正在使用
        self.lock = self.coordinator.lock  # 绑定同一个资源互斥锁
        self.is_participant = True  # 是否是参与者的标志

    # TODO:参与者只负责向协调者的处理请求的队列放请求，然后等待响应
    #   为了实现选举，需要增加选举实现的相关方法，例如检测到协调者超时没有响应则发起选举，基于贪心算法，发送的选举
    #   请求应当是从线程号最大的开始递减，直到选举成功或自己成为被选举者。因此对于每一个上一任协调者来说，都应当有
    #   一个线程复活后断线重连的过程，重新发起选举成为协调者，因此应当从以上方面着手实现选举算法
    def start(self):
        while 1:
            self.coordinator_thread_index = self.coordinator.index  # 更新当前协调者线程在线程列表的索引
            if self.coordinator_thread_index < self.thread_id:
                print(f'参与者{self.participant_id}:检测到我的线程号大于当前协调者，发起选举!')
                self.election_2()  # 第二种情况选举，自己的线程号大于当前协调者的索引
            if self.get_response:  # 如果请求已被处理，则可以发起下一次请求
                self.get_response = False
                self.request_time = datetime.now()
                self.send_request()
                self.working()  # 进入工作阻塞状态，直到收到响应
            if not self.is_participant:  # 如果自己已经不是参与者，应当退出
                return
            time.sleep(2)

    def send_request(self):
        self.request_list.append(f'{self.request_time}_{self.participant_id}')
        self.request_list.sort()
        print(f'参与者{self.participant_id}:已于{self.request_time} 发送请求，正在等待响应！')

    def working(self):
        while 1:
            response_obj = self.request_list[0]  # 协调者当前应当处理的请求
            if response_obj == f'{self.request_time}_{self.participant_id}':  # 如果当前该处理的是自己的请求
                wait_start = datetime.now()  # 开始等待的时间
                while not self.get_response:
                    wait_time = (datetime.now() - wait_start).total_seconds()  # 计算等待时间
                    if wait_time > 10:  # 超过10秒未收到响应，认为当前协调者出现问题
                        print(f'参与者{self.participant_id}:检测到协调者响应超时，发起选举！')
                        self.election_1()  # 发起情况1的选举
                        break  # 跳出等待循环

            if self.get_response:  # 得到允许表示有资格
                with self.lock:  # 但是还得拿到互斥锁才能访问
                    self.is_using = True
                    print(f'参与者{self.participant_id}:请求已被协调者允许，开始访问临界资源！')
                    # TODO：此处可以为访问临界资源的相关操作,此处用睡眠1秒代替
                    time.sleep(1)
                    print(f'参与者{self.participant_id}:访问临界资源完成，可以继续工作了！')
                    self.is_using = False
                    return

    # 进行第一种情况的选举，由于得不到响应而发起选举
    def election_1(self):
        if self.thread_id < self.coordinator_thread_index:  # 如果当前自身索引小于协调者，需要判断比自己大的线程是否可以成为协调者
            self.coordinator_thread_index = self.thread_id  # 如果遍历未找到可成为协调者的线程，则默认自己成为协调者
            candidate_list = self.thread_list[self.thread_id:self.coordinator.index]
            candidate_list.reverse()  # reverse()是列表的内置方法，reverse()会改变列表（原地反转），因此无需返回值
            for thread in candidate_list:  # .reverse方法进行列表逆置
                if thread.is_alive():
                    self.coordinator_thread_index = self.thread_list.index(thread)
                    break
        else:
            return
        self.participant_list[self.coordinator_thread_index].is_participant = False
        self.coordinator.index = self.coordinator_thread_index  # 更新协调者索引值
        self.thread_list[self.coordinator_thread_index] = Thread(target=self.coordinator.start,
                                                                 name=f'coordinator_{self.coordinator_thread_index}')  # 设置线程执行协调者工作
        self.thread_list[self.coordinator_thread_index].setDaemon(True)  # 守护线程
        print(f'参与者{self.participant_id}:线程{self.coordinator_thread_index}已成为新的协调者！')
        self.thread_list[self.coordinator_thread_index].start()
        # self.thread_list[self.coordinator_thread_index].join()

    # 进行第二种情况的选举，由于自己线程id大于当前协调者索引而发起选举
    def election_2(self):
        # 先将当前协调者还原为对应的参与者
        participant = self.participant_list[self.coordinator_thread_index]
        participant.is_participant = True
        self.thread_list[self.coordinator_thread_index] = Thread(target=participant.start,
                                                                 name=f'participant_{participant.participant_id}')
        self.thread_list[self.coordinator_thread_index].setDaemon(True)  # 守护线程
        print(f'参与者{self.participant_id}:线程{self.coordinator_thread_index}已成为参与者{participant.participant_id}')
        self.thread_list[self.coordinator_thread_index].start()
        # self.thread_list[self.coordinator_thread_index].join()

        # 自己当前的线程号最大，自己成为协调者
        self.coordinator_thread_index = self.thread_id
        self.is_participant = False
        self.coordinator.index = self.coordinator_thread_index  # 更新协调者索引值
        self.thread_list[self.coordinator_thread_index] = Thread(target=self.coordinator.start,
                                                                 name=f'coordinator_{self.coordinator_thread_index}')  # 设置线程执行协调者工作
        self.thread_list[self.coordinator_thread_index].setDaemon(True)  # 守护线程
        print(f'参与者{self.participant_id}:线程{self.coordinator_thread_index}已成为新的协调者！')
        self.thread_list[self.coordinator_thread_index].start()
        # self.thread_list[self.coordinator_thread_index].join()


class Coordinator:
    def __init__(self):
        self.thread_list = []  # 工作线程列表，初始最后一个为协调者
        self.index = len(self.thread_list)  # 协调者在工作线程列表的索引
        self.thread_id = self.index  # 自己的线程id
        self.participant_list = []
        self.request_list = []
        self.response_obj = ""
        self.response_time = datetime.now()
        self.lock = Lock()  # 临界资源访问的锁，针对参与者
        self.coordinator_lock = Lock()  # 针对协调者的锁
        self.is_participant = False  # 是否是参与者的标志

    # TODO：协调者只负责处理最早的请求，然后回复，可扩展为处理的同时修改请求对象的是否收到响应的属性
    #   这样就不需要在主线程再设置一个单独的检查者线程了
    def start(self):
        while 1:
            # print(self.request_list)
            if self.is_participant and self.index != self.thread_id:
                return  # 自己不是最初的协调者，且自己已经失去协调者的资格，直接退出
            elif self.index < self.thread_id:
                print(f'线程{self.thread_id}:检测到我的线程号大于当前协调者，发起选举!')
                self.election()  # 自己的线程号大于当前协调者的索引
            with self.coordinator_lock:
                self.send_response()
            time.sleep(1)

    def send_response(self):
        if len(self.request_list) > 0:
            self.response_obj = self.request_list[0]
            # TODO: 处理当前列表中最早的请求
            self.working()
            # 删除该请求，此处使用del的目的是在删除元素的同时释放其空间，节约内存，
            # 如果仅想达到删除列表内元素的目的，也可以使用列表自带的remove方法
            del self.request_list[0]

    def working(self):
        # TODO:已扩展为处理的同时修改请求对象的是否收到响应的属性
        #   这样就不需要在主线程再设置一个单独的检查者线程了，而且可以直接处理，不需要一直循环检查
        time.sleep(random.randint(6, 12))  # 使用随机阻塞时长模拟超时，大于10则会被判超时
        response = self.response_obj.split('_')[1]  # 当前处理的参与者id
        response = int(response)
        self.participant_list[response].get_response = True  # 设置该参与者是否得到响应的标志为True
        self.response_time = datetime.now()  # 响应时间
        print(f'协调者：来自参与者{response}的请求处理完成！处理时间：{self.response_time}')
        while self.participant_list[response].is_using:
            time.sleep(0.2)  # 每0.2秒检查该参与者是否还在使用该临界资源
            continue

    # 进行第二种情况的选举，由于自己线程id大于当前协调者索引而发起选举
    def election(self):
        # 先将当前协调者还原为对应的参与者
        participant = self.participant_list[self.index]
        participant.is_participant = True
        self.thread_list[self.index] = Thread(target=participant.start,
                                              name=f'participant_{participant.participant_id}')
        self.thread_list[self.index].setDaemon(True)  # 守护线程
        print(f'线程{self.thread_id}:线程{self.index}已成为参与者{participant.participant_id}')
        self.thread_list[self.index].start()
        # self.thread_list[self.index].join()

        # 自己当前的线程号最大，自己成为协调者
        coordinator_thread_index = self.thread_id
        self.is_participant = False
        self.index = coordinator_thread_index  # 更新协调者索引值
        self.thread_list[coordinator_thread_index] = Thread(target=self.start,
                                                            name=f'coordinator_{self.thread_id}')  # 设置线程执行协调者工作
        self.thread_list[coordinator_thread_index].setDaemon(True)  # 守护线程
        print(f'线程{self.thread_id}:线程{coordinator_thread_index}已重新成为新的协调者！')
        self.thread_list[coordinator_thread_index].start()
        # self.thread_list[coordinator_thread_index].join()
